<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  
  <title>一道编程题目引发的对编译原理的回顾 | 探花需拔根</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  
    <meta name="keywords" content="Bluarry,bluarry,Blog,探花,拔根,博客,区块链,算法,acm">
  
  <meta name="description" content="一直以来，我都认为编译原理的作用不大，所以导致我对编译原理的知识忘却完了。今日刷leetcode是碰到一道判断字符串转换成数字的题目，正常来说，都是暴力模拟，我也是这么干的，但是当我了看到题解时，我眼前一亮，我觉得编译原理也不是那么无用，故而有了这篇文章的出现。">
<meta name="keywords" content="专业知识,编译原理">
<meta property="og:type" content="article">
<meta property="og:title" content="一道编程题目引发的对编译原理的回顾">
<meta property="og:url" content="/2020/06/30/20200630-编译原理复习/index.html">
<meta property="og:site_name" content="探花需拔根">
<meta property="og:description" content="一直以来，我都认为编译原理的作用不大，所以导致我对编译原理的知识忘却完了。今日刷leetcode是碰到一道判断字符串转换成数字的题目，正常来说，都是暴力模拟，我也是这么干的，但是当我了看到题解时，我眼前一亮，我觉得编译原理也不是那么无用，故而有了这篇文章的出现。">
<meta property="og:locale" content="zh.yml">
<meta property="og:image" content="/images/upload/20200630/image-20200629115223193.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630162049180.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630163142416.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630165047598.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630171101964.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630171205322.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630171513645.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630171615475.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630171717626.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630172056236.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630173022577.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630172959930.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630172900090.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630184146410.png">
<meta property="og:image" content="/images/upload/20200630/image-20200630200203772.png">
<meta property="og:updated_time" content="2020-06-30T13:01:33.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="一道编程题目引发的对编译原理的回顾">
<meta name="twitter:description" content="一直以来，我都认为编译原理的作用不大，所以导致我对编译原理的知识忘却完了。今日刷leetcode是碰到一道判断字符串转换成数字的题目，正常来说，都是暴力模拟，我也是这么干的，但是当我了看到题解时，我眼前一亮，我觉得编译原理也不是那么无用，故而有了这篇文章的出现。">
<meta name="twitter:image" content="/images/upload/20200630/image-20200629115223193.png">
  
  
    <link rel="icon" href="/favicon.ico">
  
  <link href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">
  <link rel="stylesheet" href="/css/style.css">
  <script src="/js/pace.min.js"></script>
  

  
  

  
<!-- Matomo -->
<script type="text/javascript">
	var _paq = window._paq || [];
	/* tracker methods like "setCustomDimension" should be called before "trackPageView" */
	_paq.push(['trackPageView']);
	_paq.push(['enableLinkTracking']);
	(function() {
	  var u="//matomo.bluarry.top/";
	  _paq.push(['setTrackerUrl', u+'matomo.php']);
	  _paq.push(['setSiteId', '3']);
	  var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0];
	  g.type='text/javascript'; g.async=true; g.defer=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s);
	})();
  </script>
  <!-- End Matomo Code -->

</head>
</html>
<body>
  <div id="container">
      <header id="header">
    <div id="banner"></div>
    <div id="header-outer">
        <div id="header-menu" class="header-menu-pos animated">
            <div class="header-menu-container">
                <a href="/" class="left">
                    <span class="site-title">探花需拔根</span>
                </a>
                <nav id="header-menu-nav" class="right">
                    
                    <a  href="/">
                        <i class="fa fa-home"></i>
                        <span>主页</span>
                    </a>
                    
                    <a  href="/archives">
                        <i class="fa fa-archive"></i>
                        <span>归档</span>
                    </a>
                    
                    <a  href="/friends">
                        <i class="fa fa-envira"></i>
                        <span>友链</span>
                    </a>
                    
                    <a  href="/about">
                        <i class="fa fa-user"></i>
                        <span>关于我</span>
                    </a>
                    
                </nav>
                <a class="mobile-header-menu-button">
                    <i class="fa fa-bars"></i>
                </a>
            </div>
        </div>
        <div id="header-row">
            <div id="logo">
                <a href="/">
                    <img src="/images/avatar/me-130x130.jpg" alt="logo">
                </a>
            </div>
            <div class="header-info">
                <div id="header-title">
                    
                    <h2>
                        清风觅影
                    </h2>
                    
                </div>
                <div id="header-description">
                    
                    <h3>
                        致需极,守静笃
                    </h3>
                    
                </div>
            </div>
            <nav class="header-nav">
                <div class="social">
                    
                        <a title="Home"  href="/">
                            <i class="fa fa-home fa-2x"></i></a>
                    
                        <a title="Github" target="_blank" href="//github.com/bluarry">
                            <i class="fa fa-github fa-2x"></i></a>
                    
                        <a title="mail" target="_blank" href="mailto://bluarry@qq.com">
                            <i class="fa fa-envelope-o fa-2x"></i></a>
                    
                </div>
            </nav>
        </div>
    </div>
</header>
      <div class="outer">
        <section id="main" class="body-wrap"><article id="post-20200630-编译原理复习" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-inner">
    
      <header class="article-header">
        
  
    <h1 class="post-title" itemprop="name">
      一道编程题目引发的对编译原理的回顾
    </h1>
    <div class="post-title-bar">
      <ul>
          
              <li>
                  <i class="fa fa-book"></i>
                  
                      <a href="/categories/默认分类/">默认分类</a>
                  
                      <a href="/categories/复习/">复习</a>
                  
                      <a href="/categories/学习分享/">学习分享</a>
                  
              </li>
          
        <li>
          <i class="fa fa-calendar"></i>  2020-06-30
        </li>
        <li>
          <i class="fa fa-eye"></i>
          <span id="busuanzi_value_page_pv"></span>
        </li>
      </ul>
    </div>
  

          
      </header>
    
    <div class="article-entry post-content" itemprop="articleBody">
      
            
            <blockquote>
<p>一直以来，我都认为编译原理的作用不大，所以导致我对编译原理的知识忘却完了。今日刷leetcode是碰到一道判断字符串转换成数字的题目，正常来说，都是暴力模拟，我也是这么干的，但是当我了看到题解时，我眼前一亮，我觉得编译原理也不是那么无用，故而有了这篇文章的出现。<br><a id="more"></a></p>
</blockquote>
<h2 id="题目相关"><a href="#题目相关" class="headerlink" title="题目相关"></a>题目相关</h2><p>具体的题目链接如下：</p>
<p><a href="https://leetcode-cn.com/problems/valid-number/solution/biao-qu-dong-fa-by-user8973/" target="_blank" rel="noopener">传送门</a></p>
<p>这里的题解用到了《编译原理》的词法分析相关知识，而我已经还回去了。。。所以在这里重新复习一下。</p>
<p>所以本文将以此题为引，重新拾起相关的编译原理知识。</p>
<h2 id="词法分析"><a href="#词法分析" class="headerlink" title="词法分析"></a>词法分析</h2><h3 id="1-从正规式到NFA"><a href="#1-从正规式到NFA" class="headerlink" title="1. 从正规式到NFA"></a>1. 从正规式到NFA</h3><p>词法分析器的构造一般方法和步骤：</p>
<ul>
<li><p><strong>描述</strong>：用正规式对模式进行描述</p>
</li>
<li><p><strong>构造NFA</strong>：为每个正规式构造一个NFA；</p>
</li>
<li><p><strong>确定化</strong>：将NFA转换成等价的DFA；</p>
</li>
<li><p><strong>最小化</strong>：优化DFA，使其状态数最少；</p>
</li>
<li><p><strong>构造词法分析器</strong>：由DFA构造词法分析器。</p>
<p>如下图所示的流程。</p>
</li>
</ul>
<p><img src="/images/upload/20200630/image-20200629115223193.png" alt="image-20200629115223193"></p>
<p>以下分割线以内的内容选读：</p>
<hr>

<h4 id="1-正规式是个啥？"><a href="#1-正规式是个啥？" class="headerlink" title="1. 正规式是个啥？"></a>1. 正规式是个啥？</h4><p>​     所谓正规式，又叫正规表达式，它是表示模式的一种重要方法。编译过程的第一个阶段，词法分析就是要将输入的源程序按照某种固定的模式将它翻译成编译器可以识别的，而将这种模式用正规式表达出来，也是做词法分析器的第一步。    </p>
<p>​    正规表达式的表达方式比较像正则表达式，建立正规表达式时，可以先定义简单的正规表达式，然后用它们构造出更复杂的正规表达式。定义在字母表正规表达式的规则如下：</p>
<p>​    a)  $ \varepsilon $是正规表达式，他表示{$ \varepsilon $}，即包含空串的集合。</p>
<p>​    b)  如果a是字母表$\Sigma$ 的符号，那么a是正规表达式，表示{a}，也就是包含符号穿a的集合。</p>
<p>​    c)  假定r和s都是正规表达式，分别表示语言L(r)和L(s),则:</p>
<p>​        i). <code>(r)|(s)</code>是正规表达式，表示 $L(r) \cup L(s)$</p>
<p>​        ii). <code>(r)(s)</code>是正规表达式，表示$L(r)L(s)$</p>
<p>​        iii). <code>(r)*</code>是正规表达式，表示$(L(r))*$</p>
<p>​        iv). <code>(r)</code>是正规表达式，表示$(L(r))$</p>
<p>​    注意，该规则式递归定义的。</p>
<h4 id="2-NFA是啥？DFA呢？"><a href="#2-NFA是啥？DFA呢？" class="headerlink" title="2. NFA是啥？DFA呢？"></a>2. NFA是啥？DFA呢？</h4><blockquote>
<p> 所谓NFA，即不确定的有穷自动机，是一个由以下几个部分组成的数学模型：</p>
<ol>
<li>一个状态的有穷集合<code>S</code>。</li>
<li>一个输入符号集合$\Sigma$,即输入符号字母表。</li>
<li>一个转换函数move，它把由状态和符号组成的二元组映射到状态集合。</li>
<li>状态${s_0}$是唯一的开始或终止状态。</li>
<li>状态集合<code>F</code>是接受(或终止)状态集合。</li>
</ol>
</blockquote>
<p>NFA可以用带标记的有向图表示，成为转换图，其节点是状态，有标记的边表示转换函数。</p>
<p>下图给出了识别语言<code>(a|b)*abb</code>的NFA的转换图。这个NFA的状态集合是<code>{0,1,2,3}</code>,输入符号表<code>{a,b}</code>,状态0是开始状态，状态3是接受状态，用双圈表示。</p>
<p><img src="/images/upload/20200630/image-20200630162049180.png" alt="image-20200630162049180"></p>
<blockquote>
<p>所谓DFA，即确定的有穷自动机，是不确定的有穷自动机的特例，其中:</p>
<ol>
<li>没有一个状态具有 $ \varepsilon $转换，即在输入上的转换。</li>
<li>对每个状态s和输入符号a，最多只有一条标记为a的边离开s。</li>
</ol>
<p>确定的DFA在任何状态下，对任一输入符号，最多只有一个转换。</p>
</blockquote>
<p>同样对于上边的例子，同样是识别语言<code>(a|b)*abb</code>DFA转换图，想要的DFA转换图如下:</p>
<p><img src="/images/upload/20200630/image-20200630163142416.png" alt="image-20200630163142416"></p>
<h4 id="3-它们俩有啥不同的？"><a href="#3-它们俩有啥不同的？" class="headerlink" title="3. 它们俩有啥不同的？"></a>3. 它们俩有啥不同的？</h4><p>其实从定义可以看出来，NFA最大的特点是它的不确定性，即在当前状态下对同以自负有多于一个的下一状态转移。</p>
<ul>
<li>定义: move函数是1对多的。对于上边的例子，NFA的move函数为:</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">move=&#123;move(0,1)=0,move(0,a)=1,move(0,b)=0,....&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>状态转换图： 统一状态有多于一条边标记相同自负转移到不同的状态:</li>
</ul>
<p><img src="/images/upload/20200630/image-20200630165047598.png" alt="image-20200630165047598" style="zoom:150%;"></p>
<p>我相信你已经明白了它俩的区别了，NFA识别记号存在的问题：</p>
<ul>
<li>只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。</li>
<li>识别过程需要大量的回溯，时间复杂度升高且算法趋于复杂。</li>
</ul>
<hr>

<p>说到构造DFA，我们为啥不直接从正规式直接构造呢？</p>
<ul>
<li>机器构造需要规范算法。</li>
<li>正规式到NFA：有规范的一对一构造算法。</li>
<li>DFA到分析器：有便于记号识别的算法。</li>
</ul>
<p>从正规式到NFA的常用算法: <em>Thompson算法</em></p>
<blockquote>
<p>输入: 字母表 $\Sigma$上的正规式r</p>
<p>输出： 接收L(r)的NFA N</p>
<p>方法如下：</p>
<ol>
<li>对$\varepsilon $，构造NFA $N(\varepsilon)$接受${\varepsilon}$;</li>
</ol>
<p><img src="/images/upload/20200630/image-20200630171101964.png" alt="image-20200630171101964" style="zoom:150%;"></p>
<ol>
<li>对$\Sigma$上的每个字符a，构造NFA N(a)接受{a};</li>
</ol>
<p><img src="/images/upload/20200630/image-20200630171205322.png" alt="image-20200630171205322" style="zoom:150%;"></p>
<ol>
<li><p>若N(p)和N(q)是正规式p和q的NFA，则</p>
<p>a. 对正规式<code>p|q</code>，构造NFA N(p|q)接受$L(p) \cup  L(q)$;</p>
<p><img src="/images/upload/20200630/image-20200630171513645.png" alt="image-20200630171513645" style="zoom:150%;"></p>
<p>b. 对正规式<code>pq</code>,构造NFA N(pq)接受L(p)L(q)</p>
<p><img src="/images/upload/20200630/image-20200630171615475.png" alt="image-20200630171615475" style="zoom:150%;"></p>
<p>c. 对正规式p<em>，构造NFA N(p</em>)接受L(p*);</p>
<p><img src="/images/upload/20200630/image-20200630171717626.png" alt="image-20200630171717626" style="zoom:150%;"></p>
<p>d. 对于正规式(p)，使用p本身的NFA，不再构造。</p>
</li>
</ol>
</blockquote>
<p>例： 使用ThomPsons算法构造正规式<code>r=(a|b)*abb</code>的NFA N(r)。</p>
<p>解： 首先分解正规式，自下而上分解树形结构如下:</p>
<p><img src="/images/upload/20200630/image-20200630172056236.png" alt="image-20200630172056236" style="zoom:150%;"></p>
<p>然后开始构造：</p>
<ul>
<li>a|b</li>
</ul>
<p><img src="/images/upload/20200630/image-20200630173022577.png" alt="image-20200630173022577" style="zoom:150%;"></p>
<ul>
<li>(a|b)*</li>
</ul>
<p><img src="/images/upload/20200630/image-20200630172959930.png" alt="image-20200630172959930" style="zoom:150%;"></p>
<ul>
<li>结果</li>
</ul>
<p><img src="/images/upload/20200630/image-20200630172900090.png" alt="image-20200630172900090" style="zoom:150%;"></p>
<h3 id="2-从NFA到DFA"><a href="#2-从NFA到DFA" class="headerlink" title="2. 从NFA到DFA"></a>2. 从NFA到DFA</h3><p>​    上一节已经讲过，NFA进行匹配时，需要遍历所有可能的情况才能找到当输入是否能别识别，所以我们需要将NFA进行确定化。</p>
<p>并行法确定化不怎么实用，这里不讲了，只讲相关概念。</p>
<pre><code>&gt; $\varepsilon-闭包(T)$: 从状态T出发，不经任何字符到达的状态全体。
&gt;
&gt; smove(S,a): 从状态T出发，不经任何字符达到的状态全体。与move(s,a)的唯一区别： 用状态集取代状态。
</code></pre><p>这里讲子集法构造DFA。</p>
<p>算法的伪代码如下：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">Dstates=&#123; $\varepsilon-闭包(T)$ &#125;</span><br><span class="line">while Dstats有未标记状态T loop</span><br><span class="line">	标记T；</span><br><span class="line">	for 每个字符a loop</span><br><span class="line">		U:= $\varepsilon-闭包(smove(T,a))$</span><br><span class="line">		if U非空 then</span><br><span class="line">			Dtran[T,a]:=U;</span><br><span class="line">			if U不在Dstates中 then</span><br><span class="line">				U作为未标记状态加入Dstates;</span><br><span class="line">			end if</span><br><span class="line">		end if</span><br><span class="line">	end loop;</span><br><span class="line">end loop;</span><br></pre></td></tr></table></figure>
<p>这算法看的我很懵逼。。。所以直接从例子着手吧。</p>
<p>上一届已经给出了正规式<code>r=(a|b)*abb</code>的NFA N(r)，接下来用上述算法来构造对应的DFA：</p>
<p><code>:=</code> 表示 将前面的状态集定义为后面的字母表示</p>
<ol>
<li>$\varepsilon-闭包({0}=\{0,1,2,4,7\}) := A$</li>
<li>$\varepsilon-闭包(smove(A,a)):=\{3,8,6,7,1,2,4\}:=B$</li>
<li>$\varepsilon-闭包(smove(A,b))=\{5,6,7,1,2,4\}:=C$</li>
<li>$\varepsilon-闭包(smove(B,a))=\{3,8,6,7,1,2,4\} ==B$</li>
<li>$\varepsilon-闭包(smove(B,b))=\{5,9,6,7,1,2,4\} :=D$</li>
<li>$\varepsilon-闭包(smove(C,a))=\{3,8,6,7,1,2,4\} ==B$</li>
<li>$\varepsilon-闭包(smove(C,a))=\{5,6,7,1,2,4\} ==C$</li>
<li>$\varepsilon-闭包(smove(D,a))=\{3,8,6,7,1,2,4\} ==B$</li>
<li>$\varepsilon-闭包(smove(D,b))=\{5,10,6,7,1,2,4\} :=E$</li>
<li>$\varepsilon-闭包(smove(E,a))=\{3,8,6,7,1,2,4\} ==B$</li>
<li>$\varepsilon-闭包(smove(E,b))=\{3,8,6,7,1,2,4\} ==C$</li>
</ol>
<p>将上述的DFA画图，如下所示:</p>
<p><img src="/images/upload/20200630/image-20200630184146410.png" alt="image-20200630184146410" style="zoom:150%;"></p>
<h3 id="3-最小化DFA"><a href="#3-最小化DFA" class="headerlink" title="3. 最小化DFA"></a>3. 最小化DFA</h3><p>最小化DFA的算法如下：</p>
<blockquote>
<p>输入： DFA D=$\{S,\Sigma,move,s0,F\}$</p>
<p>输出:   等价的$D’=\{S’,\Sigma,move’,s0’,F’\}(D’状态数最少)$</p>
<p>方法执行步骤如下：</p>
<ol>
<li><p>初始划分$\prod {\rm{ = \{ S - F,F1,F2,}}…{\rm{\} }}$,其中，Fi是F的子集，接受不同记号。</p>
</li>
<li><p>应用下述过程构造新的划分 ${\prod_{new}} $:</p>
<p>for $\prod$的每一个组G loop</p>
<p>​    划分G，G的两个状态s和t在同一组的充要条件：</p>
<p>​        $\forall {\rm{a}}(move(s,a) \in Gi \wedge move(t,a) \in Gi) $</p>
<p>​    用新划分的组替代G，形成新的划分${\prod_{new}} $</p>
<p>end loop;</p>
<ol>
<li><p>若${\prod<em>{new}} = \prod$则 $${\prod</em>{final}:=\prod} <script type="math/tex">且转 4；否则，</script>\prod=:{\prod_{new}} $$且转2；</p>
</li>
<li><p>在${\prod_{final}}$每个组中选一个代表si’,是的D中从Gi所有状态出发的状态转移D‘中均从si’出发，D中所有转向Gi中的状态转移在D’中均转向si’。含有D中s0的状态组G0的代表s0’称为D’的初态，D中所有含F中状态的Gj的代表sj’构成D’的终态集F’；</p>
</li>
<li><p>删除死状态，即不是终态且对所有输入字符均转向其自身，或从初态不可到达的状态。</p>
</li>
</ol>
</li>
</ol>
</blockquote>
<p>总结一下，主要步骤如下：</p>
<p>1.初始划分：终态与非终态；</p>
<p>2.利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂；</p>
<p>3.由最终划分构造D’，关键是选代表和修改状态转移；</p>
<p>4.消除可能的死状态和不可达状态。</p>
<p>下面还是用上面的例子说明，DFA如上幅图所示，下载开始简化如图所示的DFA</p>
<p>解： </p>
<p>所有的状态转移为：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">m(A,a)=B, m(A,b)=C</span><br><span class="line">m(B,a)=B, m(B,b)=D</span><br><span class="line">m(C,a)=B, m(C,b)=C</span><br><span class="line">m(D,a)=B, m(D,b)=E</span><br><span class="line">m(E,a)=B, m(E,b)=C</span><br></pre></td></tr></table></figure>
<ol>
<li><p>初始化划分$\prod1=\{ABCD,E\}$</p>
</li>
<li><p>反复分裂划分中的组：</p>
<p>a). m(D,b)=E  —&gt; $\prod2=\{ABC,D,E\}$</p>
<p>b). m(B,b)=D —&gt; $\prod3=\{AC,B,D,E\}$</p>
<p>c). 所以 $\{\prod_{final}\}=\{ABC,D,E\}$</p>
</li>
<li><p>根据${\prod_{final}}$构造D‘</p>
<p>a. 用A代表AC组</p>
<p>b. 修改状态转移,用0123，代替ABDE</p>
<p><img src="/images/upload/20200630/image-20200630200203772.png" alt="image-20200630200203772" style="zoom:150%;"></p>
</li>
</ol>
<h3 id="4-由DFA构造词法分析器"><a href="#4-由DFA构造词法分析器" class="headerlink" title="4. 由DFA构造词法分析器"></a>4. 由DFA构造词法分析器</h3><h4 id="1-表驱动型的词法分析器"><a href="#1-表驱动型的词法分析器" class="headerlink" title="1. 表驱动型的词法分析器"></a>1. 表驱动型的词法分析器</h4><p>1). 由数据结构存放DFA；</p>
<p>2). 根据表结构，用最长匹配原则进行编码匹配词法。</p>
<h2 id="回到题目题解"><a href="#回到题目题解" class="headerlink" title="回到题目题解"></a>回到题目题解</h2><p>现在回过头去看题解。。。豁然开朗！！！</p>
<p>希望你也能用到这些知识吧。。</p>
<h2 id="参考书籍"><a href="#参考书籍" class="headerlink" title="参考书籍"></a>参考书籍</h2><ul>
<li>《编译原理》第一版 机械工业出版社, 李建中</li>
</ul>

            <div class="post-copyright">
    <div class="content">
        <p>最后更新： 2020年06月30日 21:01</p>
        <p>原始链接： <a class="post-url" href="/2020/06/30/20200630-编译原理复习/" title="一道编程题目引发的对编译原理的回顾">/2020/06/30/20200630-编译原理复习/</a></p>
        <footer>
            <a href="">
                <img src="/images/avatar/me-130x130.jpg" alt="bluarry">
                bluarry
            </a>
        </footer>
    </div>
</div>

      
        
            
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;">赏</a>
</div>

<div id="reward" class="post-modal reward-lay">
    <a class="close" href="javascript:;" id="reward-close">×</a>
    <span class="reward-title">
        <i class="icon icon-quote-left"></i>
        请我吃糖~
        <i class="icon icon-quote-right"></i>
    </span>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="/images/wechat_code.jpg" alt="打赏二维码">
        </div>
        <div class="reward-select">
            
            <label class="reward-select-item checked" data-id="wechat" data-wechat="/images/wechat_code.jpg">
                <img class="reward-select-item-wechat" src="/images/wechat.png" alt="微信">
            </label>
            
            
            <label class="reward-select-item" data-id="alipay" data-alipay="/images/alipay_code.jpg">
                <img class="reward-select-item-alipay" src="/images/alipay.png" alt="支付宝">
            </label>
            
        </div>
    </div>
</div>


        
    </div>
    <footer class="article-footer">
        
        
<div class="post-share">
    <a href="javascript:;" id="share-sub" class="post-share-fab">
        <i class="fa fa-share-alt"></i>
    </a>
    <div class="post-share-list" id="share-list">
        <ul class="share-icons">
          <li>
            <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=/2020/06/30/20200630-编译原理复习/&title=《一道编程题目引发的对编译原理的回顾》 — 探花需拔根&pic=images/avatar/me-130x130.jpg" data-title="微博">
              <i class="fa fa-weibo"></i>
            </a>
          </li>
          <li>
            <a class="weixin share-sns" id="wxFab" href="javascript:;" data-title="微信">
              <i class="fa fa-weixin"></i>
            </a>
          </li>
          <li>
            <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=/2020/06/30/20200630-编译原理复习/&title=《一道编程题目引发的对编译原理的回顾》 — 探花需拔根&source=
一直以来，我都认为编译原理的作用不大，所以导致我对编译原理的知识忘却完了。今日刷leetcode是碰到一道判断字符串转换成数字的题目，正常来说，都是暴力..." data-title="QQ">
              <i class="fa fa-qq"></i>
            </a>
          </li>
          <li>
            <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=/2020/06/30/20200630-编译原理复习/" data-title="Facebook">
              <i class="fa fa-facebook"></i>
            </a>
          </li>
          <li>
            <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《一道编程题目引发的对编译原理的回顾》 — 探花需拔根&url=/2020/06/30/20200630-编译原理复习/&via=" data-title="Twitter">
              <i class="fa fa-twitter"></i>
            </a>
          </li>
          <li>
            <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=/2020/06/30/20200630-编译原理复习/" data-title="Google+">
              <i class="fa fa-google-plus"></i>
            </a>
          </li>
        </ul>
     </div>
</div>
<div class="post-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;" id="wxShare-close">×</a>
    <p>扫一扫，分享到微信</p>
    <img src="" alt="微信分享二维码">
</div>

<div class="mask"></div>

        
        <ul class="article-footer-menu">
            
            
  <li class="article-footer-tags">
    <i class="fa fa-tags"></i>
      
    <a href="/tags/专业知识/" class="color5">专业知识</a>
      
    <a href="/tags/编译原理/" class="color5">编译原理</a>
      
  </li>

        </ul>
        
        

    <aside class="post-toc-pos post-toc-top" id="post-toc">
        <nav class="post-toc-wrap">
            <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#题目相关"><span class="post-toc-text">题目相关</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#词法分析"><span class="post-toc-text">词法分析</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#1-从正规式到NFA"><span class="post-toc-text">1. 从正规式到NFA</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#1-正规式是个啥？"><span class="post-toc-text">1. 正规式是个啥？</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#2-NFA是啥？DFA呢？"><span class="post-toc-text">2. NFA是啥？DFA呢？</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#3-它们俩有啥不同的？"><span class="post-toc-text">3. 它们俩有啥不同的？</span></a></li></ol></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#2-从NFA到DFA"><span class="post-toc-text">2. 从NFA到DFA</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#3-最小化DFA"><span class="post-toc-text">3. 最小化DFA</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#4-由DFA构造词法分析器"><span class="post-toc-text">4. 由DFA构造词法分析器</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#1-表驱动型的词法分析器"><span class="post-toc-text">1. 表驱动型的词法分析器</span></a></li></ol></li></ol></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#回到题目题解"><span class="post-toc-text">回到题目题解</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#参考书籍"><span class="post-toc-text">参考书籍</span></a></li></ol>
        </nav>
    </aside>
    

<nav id="article-nav">
  
    <a href="/2020/08/17/windows/linxu使用时用到的问题/" id="article-nav-newer" class="article-nav-link-wrap">

      <span class="article-nav-title">
        <i class="fa fa-hand-o-left" aria-hidden="true"></i>
        
          windows/linxu使用时遇到的问题
        
      </span>
    </a>
  
  
    <a href="/2020/06/28/fabric链码API及相关开发实例/" id="article-nav-older" class="article-nav-link-wrap">
      <span class="article-nav-title">fabric链码API及相关开发实例</span>
      <i class="fa fa-hand-o-right" aria-hidden="true"></i>
    </a>
  
</nav>




    <!-- HTML页面布局 -->
    <div id="tab-list">
        <ul id="ul1">
            
            
            
            <li id="gittalk" style="width: 25%;">gittalk</li>
            
            
            <li id="valine" style="width: 25%;">valine</li>
            
        </ul>
         
        
          
        <div id="dv_gitment" class="hide">
            <div id="git_comments"></div>;
        </div>
        
        
        <div id="dv_vment" class="show">
            <div class="comments vcomment" id="vcomments"></div>
        </div>
        
    </div>

    <script src="/js/tablist.js"></script>
   

    
        
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">
<script src="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>
<script src="https://cdn.bluarry.top/cdn/js/md5.min.js"></script>
<!--<div id="git_comments"></div>-->
<script>
    // var gitment = new Gitment({
    //     owner: 'bluarry',
    //     repo: 'blog_comment',
    //     oauth: {
    //         client_id: '5c95f5b820d109c8f5c1',
    //         client_secret: 'f1cfe5b08f9a55923ba26a9ec8855b631002ad18',
    //     },
    // })
    var hrefs=location.href;
    var links=hrefs.split('/');
    var cr="";
    for (var i=0;i<Math.min(7,links.length);i++) {
        cr+=links[i];
    }
    console.log(cr);

    var gitalk = new Gitalk({
        clientID: '5c95f5b820d109c8f5c1', //Client ID
        clientSecret: 'f1cfe5b08f9a55923ba26a9ec8855b631002ad18', //Client Secret
        repo: 'blog_comment',//仓库名称
        owner: 'bluarry',//仓库拥有者
        admin: ['bluarry'],
        id: md5(cr),      // Ensure uniqueness and length less than 50
        distractionFreeMode: false  // Facebook-like distraction free mode
    });
    gitalk.render('git_comments');
</script>


    
        <!-- Valine Comments -->
<!-- <div class="comments vcomment" id="vcomments"></div>-->
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script>
<!-- Valine Comments script -->
<script>
    var GUEST_INFO = ['nick','mail','link'];
    var guest_info = 'nick,mail'.split(',').filter(function(item){
        return GUEST_INFO.indexOf(item) > -1
    });
    new Valine({
        el: '#vcomments',
        notify: 'true' == 'true',
        verify: 'false' == 'true',
        appId: "DRrkhLYTmB6QwGy6sI6vCH8C-gzGzoHsz",
        appKey: "M4A4lrKwbixQmmeO5lVdY5l2",
        avatar: "mm",
        placeholder: "少侠，留下你的评论吧",
        guest_info: guest_info.length == 0 ? GUEST_INFO : guest_info,
        pageSize: "10"
    })
</script>
<!-- Valine Comments end -->

    


    </footer>
  </div>
</article>

  <script type="text/x-mathjax-config">
MathJax.Hub.Config({
    tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    }
});

MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';                 
    }       
});
</script>

<!-- 
    <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML"></script> 
-->

<script type="text/javascript" src="https://res.ailemon.net/mathjax/2.7.5/MathJax.js?config=default&amp;ver=1.3.11"></script>

<!--
<script type="text/javascript" src="https://src.ailemon.me/mathjax/2.7.5/MathJax.js?config=default&amp;ver=1.3.11"></script>
-->



</section>
        
      </div>
      <footer id="footer">
  <div class="outer">
    <div id="footer-info" class="inner">
      
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        <i class="fa fa-user"></i>&nbsp;&nbsp;<span id="busuanzi_value_site_uv"></span>
    </span>&nbsp;&nbsp;|&nbsp;&nbsp;
    <span id="busuanzi_container_site_pv" style='display:none'>
        <i class="fa fa-eye"></i> &nbsp;&nbsp;<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


      <p>
      &copy; 2016-2021 &nbsp;&nbsp;<i style="color: red;" class="fa fa-heart"></i>&nbsp;&nbsp; bluarry
      备案号: <a style="color: #999;" href="http://www.beian.miit.gov.cn/" target="_blank">陕ICP备2020012959号</a>
    </p>

    </div>
  </div>
</footer>
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<script src="//cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>
<script>
  var mihoConfig = {
      root: "",
      animate: true,
      isHome: false,
      share: true,
      reward: 1
  }
</script>
<div class="sidebar">
    <div id="sidebar-search" title="Search">
        <i class="fa fa-search"></i>
    </div>
    <div id="sidebar-category" title="Categories">
        <i class="fa fa-book"></i>
    </div>
    <div id="sidebar-tag" title="Tags">
        <i class="fa fa-tags"></i>
    </div>
    <div id="sidebar-top">
        <span class="sidebar-top-icon"><i class="fa fa-angle-up"></i></span>
    </div>
</div>
<div class="sidebar-menu-box" id="sidebar-menu-box">
    <div class="sidebar-menu-box-container">
        <div id="sidebar-menu-box-categories">
            <a class="category-link" href="/categories/linux/">linux</a><a class="category-link" href="/categories/linux-学习/">linux 学习</a><a class="category-link" href="/categories/linux-学习-acm-onlinejudge-hustoj/">linux 学习 acm onlinejudge hustoj</a><a class="category-link" href="/categories/学习分享/">学习分享</a><a class="category-link" href="/categories/数据结构/">数据结构</a><a class="category-link" href="/categories/经验分享/">经验分享</a><a class="category-link" href="/categories/经验分享/学习分享/">学习分享</a><a class="category-link" href="/categories/默认分类/">默认分类</a><a class="category-link" href="/categories/默认分类/复习/">复习</a><a class="category-link" href="/categories/默认分类/复习/学习分享/">学习分享</a><a class="category-link" href="/categories/默认分类/学习分享/">学习分享</a><a class="category-link" href="/categories/默认分类/生活杂谈/">生活杂谈</a><a class="category-link" href="/categories/默认分类/经验分享/">经验分享</a><a class="category-link" href="/categories/默认分类/经验分享/学习分享/">学习分享</a>
        </div>
        <div id="sidebar-menu-box-tags">
            <a href="/tags/Java/" style="font-size: 10px;">Java</a> <a href="/tags/acm/" style="font-size: 12.86px;">acm</a> <a href="/tags/android/" style="font-size: 11.43px;">android</a> <a href="/tags/c/" style="font-size: 14.29px;">c++</a> <a href="/tags/fabric/" style="font-size: 11.43px;">fabric</a> <a href="/tags/kali/" style="font-size: 10px;">kali</a> <a href="/tags/linux/" style="font-size: 15.71px;">linux</a> <a href="/tags/linux学习/" style="font-size: 10px;">linux学习</a> <a href="/tags/mac/" style="font-size: 10px;">mac</a> <a href="/tags/mfc/" style="font-size: 10px;">mfc</a> <a href="/tags/onlinejudge/" style="font-size: 10px;">onlinejudge</a> <a href="/tags/sqlite/" style="font-size: 10px;">sqlite</a> <a href="/tags/sqlite3/" style="font-size: 11.43px;">sqlite3</a> <a href="/tags/ss/" style="font-size: 10px;">ss</a> <a href="/tags/vs/" style="font-size: 11.43px;">vs</a> <a href="/tags/xposed/" style="font-size: 10px;">xposed</a> <a href="/tags/xposed模块/" style="font-size: 10px;">xposed模块</a> <a href="/tags/专业知识/" style="font-size: 10px;">专业知识</a> <a href="/tags/侧链/" style="font-size: 10px;">侧链</a> <a href="/tags/内网穿透/" style="font-size: 10px;">内网穿透</a> <a href="/tags/区块链/" style="font-size: 11.43px;">区块链</a> <a href="/tags/复习/" style="font-size: 10px;">复习</a> <a href="/tags/学习/" style="font-size: 18.57px;">学习</a> <a href="/tags/安卓/" style="font-size: 12.86px;">安卓</a> <a href="/tags/小技巧/" style="font-size: 17.14px;">小技巧</a> <a href="/tags/数据库/" style="font-size: 10px;">数据库</a> <a href="/tags/数据结构/" style="font-size: 10px;">数据结构</a> <a href="/tags/日常使用问题/" style="font-size: 10px;">日常使用问题</a> <a href="/tags/最小生成树/" style="font-size: 11.43px;">最小生成树</a> <a href="/tags/最短路径/" style="font-size: 10px;">最短路径</a> <a href="/tags/比特币/" style="font-size: 11.43px;">比特币</a> <a href="/tags/算法/" style="font-size: 12.86px;">算法</a> <a href="/tags/算法笔记/" style="font-size: 11.43px;">算法笔记</a> <a href="/tags/经验/" style="font-size: 20px;">经验</a> <a href="/tags/编译原理/" style="font-size: 10px;">编译原理</a> <a href="/tags/翻译/" style="font-size: 10px;">翻译</a> <a href="/tags/自然计算/" style="font-size: 10px;">自然计算</a>
        </div>
    </div>
    <a href="javascript:;" class="sidebar-menu-box-close">&times;</a>
</div>
<div class="mobile-header-menu-nav" id="mobile-header-menu-nav">
    <div class="mobile-header-menu-container">
        <span class="title">Menus</span>
        <ul class="mobile-header-menu-navbar">
            
            <li>
                <a  href="/">
                    <i class="fa fa-home"></i><span>主页</span>
                </a>
            </li>
            
            <li>
                <a  href="/archives">
                    <i class="fa fa-archive"></i><span>归档</span>
                </a>
            </li>
            
            <li>
                <a  href="/friends">
                    <i class="fa fa-envira"></i><span>友链</span>
                </a>
            </li>
            
            <li>
                <a  href="/about">
                    <i class="fa fa-user"></i><span>关于我</span>
                </a>
            </li>
            
        </ul>
    </div>
    <div class="mobile-header-tag-container">
        <span class="title">Tags</span>
        <div id="mobile-header-container-tags">
            <a href="/tags/Java/" style="font-size: 10px;">Java</a> <a href="/tags/acm/" style="font-size: 12.86px;">acm</a> <a href="/tags/android/" style="font-size: 11.43px;">android</a> <a href="/tags/c/" style="font-size: 14.29px;">c++</a> <a href="/tags/fabric/" style="font-size: 11.43px;">fabric</a> <a href="/tags/kali/" style="font-size: 10px;">kali</a> <a href="/tags/linux/" style="font-size: 15.71px;">linux</a> <a href="/tags/linux学习/" style="font-size: 10px;">linux学习</a> <a href="/tags/mac/" style="font-size: 10px;">mac</a> <a href="/tags/mfc/" style="font-size: 10px;">mfc</a> <a href="/tags/onlinejudge/" style="font-size: 10px;">onlinejudge</a> <a href="/tags/sqlite/" style="font-size: 10px;">sqlite</a> <a href="/tags/sqlite3/" style="font-size: 11.43px;">sqlite3</a> <a href="/tags/ss/" style="font-size: 10px;">ss</a> <a href="/tags/vs/" style="font-size: 11.43px;">vs</a> <a href="/tags/xposed/" style="font-size: 10px;">xposed</a> <a href="/tags/xposed模块/" style="font-size: 10px;">xposed模块</a> <a href="/tags/专业知识/" style="font-size: 10px;">专业知识</a> <a href="/tags/侧链/" style="font-size: 10px;">侧链</a> <a href="/tags/内网穿透/" style="font-size: 10px;">内网穿透</a> <a href="/tags/区块链/" style="font-size: 11.43px;">区块链</a> <a href="/tags/复习/" style="font-size: 10px;">复习</a> <a href="/tags/学习/" style="font-size: 18.57px;">学习</a> <a href="/tags/安卓/" style="font-size: 12.86px;">安卓</a> <a href="/tags/小技巧/" style="font-size: 17.14px;">小技巧</a> <a href="/tags/数据库/" style="font-size: 10px;">数据库</a> <a href="/tags/数据结构/" style="font-size: 10px;">数据结构</a> <a href="/tags/日常使用问题/" style="font-size: 10px;">日常使用问题</a> <a href="/tags/最小生成树/" style="font-size: 11.43px;">最小生成树</a> <a href="/tags/最短路径/" style="font-size: 10px;">最短路径</a> <a href="/tags/比特币/" style="font-size: 11.43px;">比特币</a> <a href="/tags/算法/" style="font-size: 12.86px;">算法</a> <a href="/tags/算法笔记/" style="font-size: 11.43px;">算法笔记</a> <a href="/tags/经验/" style="font-size: 20px;">经验</a> <a href="/tags/编译原理/" style="font-size: 10px;">编译原理</a> <a href="/tags/翻译/" style="font-size: 10px;">翻译</a> <a href="/tags/自然计算/" style="font-size: 10px;">自然计算</a>
        </div>
    </div>
</div>
<div class="search-wrap">
    <span class="search-close">&times;</span>
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
            <i class="icon icon-lg icon-chevron-left"></i>
        </a>
        <input class="search-field" placeholder="Search..." id="keywords">
        <a id="search-submit" href="javascript:;">
            <i class="fa fa-search"></i>
        </a>
    <div class="search-container" id="search-container">
        <ul class="search-result" id="search-result">
        </ul>
    </div>
</div>

<div id="search-tpl">
    <li class="search-result-item">
        <a href="{url}" class="search-item-li">
            <span class="search-item-li-title" title="{title}">{title}</span>
        </a>
    </li>
</div>
<script src="/js/search.js"></script>
<script src="/js/main.js"></script>


  <script src="//cdn.bootcss.com/particles.js/2.0.0/particles.min.js"></script>
  <div id="particles"></div>
  <script src="/js/particles.js"></script>







  <link rel="stylesheet" href="//cdn.bootcss.com/animate.css/3.5.0/animate.min.css">
  <script src="//cdn.bootcss.com/scrollReveal.js/3.0.5/scrollreveal.js"></script>
  <script src="/js/animate.js"></script>


  <script src="/js/pop-img.js"></script>
  <script>
     $(".article-entry p img").popImg();
  </script>

  </div>
</body>
</html>